package demo3;

//牛客网:矩阵最长递增路径
// https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2?tpId=196&tqId=37184&ru=/exam/oj

import java.util.*;


class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here
        int n = matrix.length;
        int m = matrix.length;
        int[][] dp = new int[n+2][m+2];
        int[][] map = new int[n+2][m+2];
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                map[i][j] = matrix[i-1][j-1];
                dp[i][j] = 1;
            }
        }

        for(int i = 0; i<=n+1; i++) {
            map[0][i] = map[n+1][i] = -1;
        }
        for(int i = 0; i<=m+1; i++) {
            map[i][0] = map[i][m+1] = -1;
        }

        int ret = 0;

        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if(map[i-1][j] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + 1);
                if(map[i][j-1] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i][j-1] + 1);
                ret = Math.max(ret, dp[i][j]);
            }
        }

        for(int i = n; i>=1; i--) {
            for(int j = m; j>=1; j--) {
                if(map[i+1][j] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i+1][j] + 1);
                if(map[i][j+1] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i][j+1] + 1);
                ret = Math.max(ret, dp[i][j]);
            }
        }

        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if(map[i-1][j] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + 1);
                if(map[i][j-1] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i][j-1] + 1);
                ret = Math.max(ret, dp[i][j]);
            }
        }

        for(int i = n; i>=1; i--) {
            for(int j = m; j>=1; j--) {
                if(map[i+1][j] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i+1][j] + 1);
                if(map[i][j+1] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i][j+1] + 1);
                ret = Math.max(ret, dp[i][j]);
            }
        }

        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if(map[i-1][j] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + 1);
                if(map[i][j-1] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i][j-1] + 1);
                ret = Math.max(ret, dp[i][j]);
            }
        }

        for(int i = n; i>=1; i--) {
            for(int j = m; j>=1; j--) {
                if(map[i+1][j] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i+1][j] + 1);
                if(map[i][j+1] < map[i][j]) dp[i][j] = Math.max(dp[i][j], dp[i][j+1] + 1);
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret;
    }
}

//记忆化搜索
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    int n,m;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    int[][] dp = new int[1002][1003];

    public int solve (int[][] matrix) {
        // write code here
        n = matrix.length;
        m = matrix.length;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                dp[i][j] = -1;
            }
        }
        int ret = 0;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                ret = Math.max(ret, dfs(matrix,i,j)+1);
                //System.out.println(ret);
            }
        }

        return ret;
    }
    public int dfs(int[][] matrix, int x, int y) {
        if(dp[x][y] != -1) return dp[x][y];
        int len = 0;
        for(int i = 0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx >= 0 && dx < n && dy >=0 && dy < m && matrix[dx][dy] > matrix[x][y]) {
                len = Math.max(len, 1 + dfs(matrix,dx,dy));
            }
        }
        dp[x][y] = len;
        return len;
    }
}

/*

dp[i][j]: 到达i, j 时的最长递增路径

1 2
4 3

*/

/*

dp[i][j]: 到达i, j 时的最长递增路径

1 2
4 3

*/